package algorithm_demo.sort;

import java.util.Arrays;

/**
 * 选择排序
 * <p>
 * 选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。
 * 它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
 * 以此类推，直到所有元素均排序完毕。
 * <p>
 * 算法步骤
 * 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
 * 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
 * 重复第 2 步，直到所有元素均排序完毕。
 * <p>
 * 算法分析
 * 稳定性：不稳定
 * 时间复杂度 ：最佳：O(n2) ，最差：O(n2)， 平均：O(n2)
 * 空间复杂度 ：O(1)
 * 排序方式 ：In-place
 *
 * @author Api
 * @date 2022/11/18 21:58
 */
public class SelectionSort {

    public static void main(String[] args) {
        int[] arr = {8, 22, 34, 1, 3, 2, 12, 12, 3, 4, 54, 53};
        int[] ints = selectionSort(arr);
        System.out.println(Arrays.toString(ints));
    }

    public static int[] selectionSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
            System.out.println(Arrays.toString(arr));
        }
        return arr;
    }
}
